package leetcode.weekly.week319;

import leetcode.helper.H;

//Solution4Test
public class Solution4 {

	public int maxPalindromes(String s, int k) {
		int len = s.length();
		char[] cs = s.toCharArray();
		boolean[][] dp = new boolean[len][len];// [l,r]是不是回文
		for (int i = 0; i < len; i++) {
			for (int j = i; j >= 0; j--) {
				if (j == i)
					dp[j][i] = true;
				else if (j + 1 == i && cs[i] == cs[j]) {
					dp[j][i] = true;
				} else if (cs[i] == cs[j] && dp[j + 1][i - 1]) {
					dp[j][i] = true;
				}
			}
		}
		int[] dp2 = new int[len + 1];
		k--;
		for (int i = 1; i <= len; i++) {
			for (int j = i - k; j > 0; j--) {
				if (dp[j - 1][i - 1]) {
					dp2[i] = dp2[j - 1] + 1;
					break;
				}
			}
			dp2[i] = Math.max(dp2[i], dp2[i - 1]);
		}
		return dp2[len];
	}

//	public static void main(String[] args) {
//
//		Solution4 so = new Solution4();
//		so.maxPalindromes(null, 0);
//
//	}

}
